home *** CD-ROM | disk | FTP | other *** search
/ 220 Jogos / 220 jogos.iso / tiro / nave2 / Docs / Networking.Paper < prev    next >
Encoding:
Text File  |  1999-12-07  |  9.4 KB  |  203 lines
  1.  
  2.             Networking Maelstrom
  3.  
  4.                             Sam Lantinga
  5. June 2, 1996
  6.  
  7.  
  8. Design Goals:
  9.  
  10.     I originally envisioned being able to play Maelstrom
  11. one-on-one against other people over Linux SLIP lines.  We could log
  12. into a central server and play one another, similar to the way Quake (tm)
  13. is planned to be.
  14.  
  15. Design Process:
  16.  
  17.     The first idea was to create one central server that did
  18. all calculation of player movement, collision detection, etc, and then
  19. broadcast updates, every frame time, to each player.  The disadvantages
  20. of this approach are that it places a great computation load on a single
  21. machine, and requires high bandwidth to transmit the entire game state
  22. thirty times per second.  I started coding the client to duplicate some
  23. of the state calculation of the game and reduce the bandwidth requirement,
  24. but it was a great deal of work, and subtle differences in the client
  25. and server code could result in synchronization bugs.
  26.  
  27.     The next design paradigm was to have N independent games
  28. running, and have each independent game control a player.  To reduce 
  29. bandwidth, each game would run its game computations independently, and 
  30. the only traffic would be synchronization packets every frame, and keystrokes
  31. to update player actions.  Actually, the only traffic really needed is
  32. the keystroke information, but in a shoot'em up game such as Maelstrom,
  33. the frame on which keystrokes are delivered is critical.  If a game runs
  34. really fast on one machine, and a keystroke arrives from a slower player,
  35. then a player can die on one machine and still be alive on another machine.
  36. This fragments game consistency and must be avoided.  The way to avoid this
  37. is to have each game instance (player) checkpoint at every frame, and 
  38. deliver keystrokes destined for that frame.
  39.  
  40.     Creating multiple players had the unexpected side effect
  41. of requiring the game logic to be rewritten using C++ objects.  The
  42. original game logic assumed that all game objects were generic
  43. structures fit into an array, and the object at array position 0 was
  44. the player.  With multiple players there had to be a way to allow
  45. them to shoot at eachother, and for objects to interact in general
  46. ways, and in then sometimes in particular ways depending on the type
  47. of objects interacting.  This lent itself well to C++ object inheritance
  48. design, and took about three days of coding to get mostly working.
  49.  
  50.     Synchronization between running games was assured by the
  51. use of the original random number generator used in Macintosh Maelstrom,
  52. and the translation of time-based events to frame-based events.
  53. The original random number generator uses a very specific algorithm to
  54. take the random seed, translate it into a pseudo-random number and then
  55. update the random seed.  Event translation works because frames are
  56. supposed to occur exactly 30 times per second and the original event timings
  57. were always some multiple of frame times apart.  The only completely
  58. random event in the game is the completion of sound events, and the only
  59. time they are ever noticed is during thrust, and no calculation affecting
  60. the game is done at that time.  Combined, this allows multiple games,
  61. given the same seed and input, to run exactly the same over multiple 
  62. instances.
  63.  
  64.     The only problem now was how to guarantee the delivery of the same
  65. input to each instance of the game.  TCP was my first choice, as it has the
  66. advantage of reliable delivery and would guarantee that my frame packets
  67. would arrive in the correct order.  However, TCP has the disadvantages of
  68. high overhead and buffered data.  In the course of ECS152B, I learned about
  69. the slow start algorithm, congestion avoidance, and other features of TCP
  70. that makes it very suited for reliable stream data, but a poor choice for
  71. timely high speed packet transmission.  
  72.  
  73.     UDP is the perfect choice of the IP protocol suite for high-speed,
  74. low overhead packet based transmissions.  It has zero connection establishment
  75. overhead, packets are sent as soon as they are queued, and if packets are lost,
  76. with careful packet management and caching, your application can recover
  77. almost immediately.  In my final design, I use a modified stop-wait protocol
  78. that uses packet caching to do very little waiting.
  79.  
  80.     To synchronize the game we need to make sure all keystrokes arrive
  81. on the interval in which they were pressed.  The original game polls for
  82. keystrokes on every frame, and testing shows that while for most purposes
  83. polling every other frame is acceptable, but for pitched battles, the 30'th
  84. of a second resolution is critical.  This means that we need synchronization
  85. every frame.  Keystroke information can ride piggy-back on synchronization
  86. packets, so the only overhead that is important is that of the sync packets
  87. themselves.  If any player gets more than one partial frame ahead of another,
  88. we may lose synchronization, so some sort of stop and wait protocol is
  89. suggested.
  90.  
  91.     Using stop and wait protocol, the total overhead of synchronization
  92. packets, assuming a two-player game, is:
  93.  
  94.     30*(sizeof(IP header)+sizeof(UDP header)+sizeof(packet))
  95.     30*(20+20+1) = 1230 bytes per player
  96.  
  97. If we ack each frame packet, we effectively double the bandwidth to
  98. nearly 2500 bytes per second for each player.  This is far beyond the
  99. current modem IP bandwidth for 14.4Kbps modems.
  100.  
  101. If we somehow eliminate ack packets, and compress the IP header, we
  102. can reach a low bandwidth requirement of 30*(4+20+1) 750 bytes per
  103. second for each player.  At an average 200 ms round trip time, our game
  104. could reach a maximum of 10-15 frames per second -- much too low for 
  105. high speed interactive games.  Thus, the solution seems to be that 
  106. high speed modem play is infeasible over IP.  Note that without the
  107. overhead of UDP/IP communications, i.e. direct modem or null-modem
  108. connection, our bandwidth requirement goes down to 30*(1+1) bytes
  109. per second, or 60 bytes per second for each player.  You could play
  110. this over a 2400 baud modem!
  111.  
  112.     In practice, it seems that an ethernet-speed network is
  113. required to run networked Maelstrom over UDP/IP.  So, the challenge
  114. becomes reducing the overhead of the network to levels that allow the 
  115. other parts of the game to proceed at thirty frames per second.
  116.  
  117.  
  118. The Algorithm:
  119.  
  120.     Already mentioned was a modified stop and wait with little
  121. waiting.  Here's how it works.  Each frame, every player sends its
  122. current frame packet to each other player and waits for frame information
  123. from every other player.  Since this happens simultaneously, each player
  124. sends and receives the current frame packet almost instantaneously, and
  125. they continue processing the game.
  126.  
  127.     * A player will never advance the frame if it doesn't receive
  128.       frame updates from all other players.
  129.     * If it doesn't receive a frame packet within 1 second it will
  130.       rebroadcast the current frame packet.
  131.     * If a player receives a frame packet for the last frame, it will
  132.       send its previous frame packet which it has cached.
  133.     * Packets from frames farther back than the previous frame are
  134.       ignored.
  135.  
  136. In this situation, if a packet is lost, then the player waiting for it
  137. will time out, the other players will be one frame ahead, the player
  138. waiting for the packet will resend it's packet, and the player who lost
  139. the packet will resend.  The waiting player will continue, and all will
  140. be well.  It is guaranteed that no player will be more than one frame
  141. ahead in this case.
  142.  
  143. Unfortunately there is a real possibility of a lock-step problem here:
  144.  
  145.     Player 1  (frame 10)        Player 2  (frame 10)
  146.         10 -->                <-- 10
  147.         dropped packet
  148.     Player 1  (frame 10)        Player 2  (frame 11)
  149.         wait for 10            <-- 11
  150.         get 11, timeout
  151.     Player 1  (frame 10)        Player 2  (frame 11)
  152.         10 -->                <-- 10 (cached)
  153. Here player 2 has already sent the packet for 11
  154.     Player 1  (frame 11)        Player 2 (frame 11)
  155.         11 -->                wait for 11
  156.     Player 1  (frame 11)        Player 2 (frame 12)
  157.         wait for 11            <-- 12
  158.         get 12, timeout
  159.  
  160. This goes on, repeating, as the two players advance frames in lock-step,
  161. one frame per timeout.
  162.  
  163. The solution is for Player 1 to immediately resend its current frame packet
  164. if it receives a packet for the next frame.  At that point it knows that
  165. the other player has already advanced to the next frame and has already
  166. sent the packet for the current frame.  If it caches the packet for the
  167. next frame, the next time around, it just sends the packet for the next
  168. frame, and advances immediately.  The two players are now back in sync.
  169.  
  170. This assumes that few packets will be dropped or otherwise lost.
  171. This seems to be a valid assumption.  It was tested over a 32.6K link to 
  172. Australia and though the game was unplayably slow because of round trip
  173. times, dropped, lost, and timed out packets were few and far between.
  174.  
  175. The new senario:
  176.  
  177.     Player 1  (frame 10)        Player 2  (frame 10)
  178.         10 -->                <-- 10
  179.         dropped packet
  180.     Player 1  (frame 10)        Player 2  (frame 11)
  181.         get 11, cache 11, 10 -->        <-- 11
  182.     Player 1  (frame 10)        Player 2  (frame 11)
  183.         get 10                <-- 10 (cached)
  184.     Player 1  (frame 11)        Player 2  (frame 11)
  185.         11 -->                get 11
  186.     Player 1  (frame 12)        Player 2 (frame 12)
  187.         12 -->                <-- 12
  188.  
  189. The players are now synchronized again.
  190.  
  191.     This run-wait scheme works very well when you have a set
  192. of hosts that are broadcasting synchronization packets to each other at
  193. high rates.  It prevents the stop-wait syndrome, and reduces the necessity
  194. of timeouts, the main disadvantages of using UDP for small packet based
  195. communications.  It has been shown, through extensive testing, to be highly
  196. effective for frame-based network games such as Maelstrom.
  197.  
  198.     IT WORKS!!
  199.  
  200.         Anybody wanna play? :-)
  201.  
  202. (slouken@devolution.com)
  203.